#include <fstream>
#include <cstdlib>
#include <cmath>
#include <string>
#include <util.h>
#include <timer.h>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/** NOTE: Esto tiene que ser una copia exacta de ej2.cpp */	
typedef unsigned long uint32;
typedef uint32 label_nodo;
typedef uint32 peso;

/************************************************
 *     FUNCIONES DEL GENERADOR                  
 * **********************************************/

uint32 rand32() {
	uint32 r = rand();
	r = r << 16;
	return r + rand();
}


uint32 cotaInf(uint32 m_restantes, uint32 sum_x_n) {
	long aristas_sobrantes =  (long) m_restantes - (long) sum_x_n;
	
	if (aristas_sobrantes <= 0) 
			return 0;
	else 
		return (uint32) aristas_sobrantes;
}

uint32 cotaSup(uint32 nodo_x, uint32 m_restantes, uint32 n ) {
	uint32 max_aristas = m_restantes - (n - nodo_x);

	if (nodo_x < max_aristas) 
		return nodo_x;
	else
		return max_aristas;	
}



/**************************************************
 *         FUNCIONES DEL SOLVER DEL PROBLEMA
 * ************************************************/

struct arista_t {
	arista_t(label_nodo a, label_nodo b, peso c): u(a), v(b), P(c) {};
	
	label_nodo u;
	label_nodo v;
	peso P;
};


class Grafo //no orientado
{
	public:
		Grafo (uint32 cant_nodos): E()
			{
				this->n = cant_nodos;
				this->m = 0;
				this->peso_grafo = 0;
			};

		/** Requiere: 
			1)  u, v son nodos del grafo
			2)  arista (u,v) no pertenece al grafo
		**/
		void agregarArista( label_nodo u, label_nodo v, peso p)
			{
				arista_t arista(u,v,p);

				(this->E).push_back(arista);
				this->m++;
				this->peso_grafo += p;
			};
		
		peso peso_Kruskal();
		
		peso peso_Grafo() const
		{
			return this->peso_grafo;
		};
		
		const uint32 cantNodos() const {
			return this->n;
		};
		
		const uint32 cantAristas() const {
			return this->m;
		};
	
	
	private:
		uint32 n, m;
					
		vector<arista_t> E; 
		peso peso_grafo;
			
};

extern peso resolver(Grafo& G);

/** Acá empieza el generador. **/
static int gMin = 50;
static int gMax = 500;

#define REP 10

void generarMejorCaso( ostream &salida ) {
// Arbol: elegimos un arbol que tenga n nodos, de los cuales 1 tiene grado n-1 y los demas grado 1 
// unidos a este.
	Timer t;
	
	ofstream times( "t2-times-mejor.txt" );
	ofstream clocks( "t2-clocks-mejor.txt" );
	
	srand( time( 0 ) );

	// Genera los casos
	for ( int i = gMin; i <= gMax; i++ ) {	
	resultado_t TT = 0;
	for ( int w = 0; w < REP; w++ ) {
		
		uint32 nodos = i;
		uint32 aristas = nodos - 1;
		
		uint32 x = 0, y = 0, z;
		
		uint32 MAX_SUMA = 0x7FFFFFF;   // MAX_SUMA < 2^31
		uint32 MAX_PESO_ARISTA = MAX_SUMA / aristas - 1;
		z = 1 + rand32() % MAX_PESO_ARISTA;
		
		
		Grafo G(nodos);	

		x = rand32()  %  nodos;
		for (y=0; y < nodos; y++) {
			if (y!= x)
				G.agregarArista(x,y,z);
		}
	
		t.comenzar();		
		resolver(G);
		t.terminar();
		
		TT = TT + t.getTiempo();
		}
		
		times << i + i << ' ' << TT / REP << endl;
		clocks << i + i << ' ' << t.getCiclos() << endl;	
		i++;
	}	
	
	
}

void generarPeorCaso( ostream &salida ) {
// Grafo completo

	ofstream times( "t2-times-peor.txt" );
	ofstream clocks( "t2-clocks-peor.txt" );
	Timer t;
	
	srand( time( 0 ) );

	// Genera los casos
	for ( int i = gMin; i <= gMax; i++ ) {	
	resultado_t TT = 0;
	for ( int w = 0; w < REP; w++ ) {
	
		uint32 nodos = i;
		uint32 aristas = (nodos * (nodos - 1)) /2; 
		
		uint32 x = 0, y = 0, z;
		
		uint32 MAX_SUMA = 0x7FFFFFF;   // MAX_SUMA < 2^31
		uint32 MAX_PESO_ARISTA = MAX_SUMA / aristas - 1;
		z = 1 + rand32() % MAX_PESO_ARISTA;
		
		
		Grafo G(nodos);	

		for (x=0; x < nodos; x++)
			for ( y=0; y < x; y++) {
				G.agregarArista(x,y,z);
			}
	
		t.comenzar();						
		resolver(G);
		t.terminar();

		TT = TT + t.getTiempo();
		}
		
		times << i + i << ' ' << TT/REP << endl;
		clocks << i + i << ' ' << t.getCiclos() << endl;	
		i++;
	}
}


/*
void generarCasosAleatorios( ostream &salida ) {
	int conexiones, rutas;
	int conexion1, conexion2, longitud;
	Timer t;
	
	ofstream times( "t2-times-aleatorio.txt" );
	ofstream clocks( "t2-clocks-aleatorio.txt" );
	ofstream archivo_entrada("e2-input.txt");
	
	srand( time( 0 ) );


	// Genera los casos
	for ( int i = gMin; i <= gMax; i++ ) {	
		uint32 nodos = i;		
	
		for (int j= i-1;  j<= (i * (i - 1)) /2 ; j++) {
		
			uint32 aristas = j;
		
			uint32 x = 0, y = 0, z = 0;
			uint32 MAX_SUMA = 0x7FFFFFE;   // MAX_SUMA < 2^31

			uint32 SUMA = 0, MAX_PESO_ARISTA;
			archivo_entrada << nodos << " " << aristas << '\n';	
		
			bool NEXT = true;
			uint32 aristas_x = 0;
			uint32 sum_x_n = (nodos * (nodos - 1)) /2; 
		
			while (aristas) {
			
				MAX_PESO_ARISTA  = MAX_SUMA - (aristas - 1); 
				z = 1 + rand32() % MAX_PESO_ARISTA;

				if (NEXT) {
					NEXT = false;
					x++;
					y=0;
					
					sum_x_n -= x; 
				
					uint32 base = cotaInf(aristas, sum_x_n) + 1;
					uint32 offset = cotaSup(x,aristas, nodos) - cotaInf(aristas, sum_x_n);
					if (offset > 0)
						aristas_x =  base + rand32() % offset;
					else
						aristas_x = base;
							
				}

				if (!NEXT) {

					while ( !( rand32() % 2 ) && (aristas_x < (x-y)))
						y++;
										
					// usar ese nodo Y			
					aristas_x--;
									
				}
						
				archivo_entrada << x << " " << y << " " << z << '\n';  
				y++;
				
				if (aristas_x == 0) NEXT = true;

				SUMA += z;
				MAX_SUMA -= z;
				aristas--;			
			}
		}
	}

	int a=0, b=0;
	archivo_entrada << a << " " << b << '\n';
	archivo_entrada.close();
	
	// Abrimos el archivo recien creado
	
	ifstream entrada("e2-input.txt");	
	
	
	//-------- Lee los casos	 ------------//
	while ( entrada.good() ) {
		entrada >> conexiones >> rutas;
		
		Grafo G(conexiones);

		if ( !entrada.good() || (conexiones==0 && rutas==0))
				break;
		
		for ( int c = 0; c < rutas; c++ ) {

			entrada >> conexion1 >> conexion2 >> longitud;
			
			G.agregarArista(conexion1,conexion2,longitud);
			
		}
		
		t.comenzar();		
		salida << resolver(G) << endl;
		t.terminar();

		times << 2*conexiones << ' ' << 2*rutas << ' ' << t.getTiempo() << endl;
		clocks << 2*conexiones << ' ' << 2*rutas << ' ' << t.getCiclos() << endl;	
	}
}
*/



// 1) Fija cantidad de nodos
//
// Se fijara |V| en gMin y se hara variar |E| entre |V|-1 y |V|(|V|-1)/2


// 2) Fija cantidad de aristas
// 
// Se fijara |E| en gMax  y se ira variando |V| entre gMin y gMax
// NOTA: gMax no debe supera la cota maxima de aristas para |V|=gMin

void generarCasosAleatorios( ostream &salida ) {
	Timer t;
	
	ofstream times_vfijo( "t2-times-vfijo.txt" );
	ofstream times_efijo( "t2-times-efijo.txt" );
	
	ofstream clocks_vfijo( "t2-clocks-vfijo.txt" );
	ofstream clocks_efijo( "t2-clocks-efijo.txt" );	

	srand( time( 0 ) );

	// Genera los casos
	// 1) Cantidad fija de nodos
	uint32 nodos = gMin;
	uint32 aristas;
		
	for (uint32 j= nodos-1;  j <= (nodos * (nodos - 1)) /2 ; j++) {
	uint32  aristas_aux = j;		
	resultado_t TT = 0;
	for ( int w = 0; w < REP; w++ ) {
		
		uint32 sum_x_n = (nodos * (nodos - 1)) /2; 
		aristas = j;
						
		Grafo G(nodos);
		
		uint32 x = 0, y = 0, z = 0;
		uint32 MAX_SUMA = 0x7FFFFFE;   // MAX_SUMA < 2^31

		uint32 SUMA = 0, MAX_PESO_ARISTA;
		
		bool NEXT = true;
		uint32 aristas_x = 0;
		
		while (aristas) {
	
			MAX_PESO_ARISTA  = MAX_SUMA - (aristas - 1); 
			z = 1 + rand32() % MAX_PESO_ARISTA;

			if (NEXT) {
				NEXT = false;
				x++;
				y=0;
				
				sum_x_n -= x; 
			
				uint32 base = cotaInf(aristas, sum_x_n) + 1;
				uint32 offset = cotaSup(x,aristas, nodos) - cotaInf(aristas, sum_x_n);
				if (offset > 0)
					aristas_x =  base + rand32() % offset;
				else
					aristas_x = base;
						
			}
				if (!NEXT) {
					while ( !( rand32() % 2 ) && (aristas_x < (x-y)))
					y++;
									
				// usar ese nodo Y			
				aristas_x--;
								
			}
			G.agregarArista(x,y,z); //inserta arista
					
			y++;
			
			if (aristas_x == 0) NEXT = true;
				SUMA += z;
			MAX_SUMA -= z;
			aristas--;			
		}
		
		t.comenzar();		
		resolver(G);
		t.terminar();
		
		TT = TT + t.getTiempo();
		}		
		
		times_vfijo << ' ' << 2*aristas_aux << ' ' << TT / REP << endl;
		clocks_vfijo << ' ' << 2*aristas_aux << ' ' << t.getCiclos() << endl;	
		
		
	}


	// 2) Cantidad fija de aristas  (TO DO)
	for (int j= gMin;  j < gMax ; j++) {
	
	resultado_t TT = 0;
	for ( int w = 0; w < REP; w++ ) {
		
		nodos = j;
		aristas = gMax;
		
		Grafo G(nodos); //Crea grafo
		
		uint32 x = 0, y = 0, z = 0;
		uint32 MAX_SUMA = 0x7FFFFFE;   // MAX_SUMA < 2^31

		uint32 SUMA = 0, MAX_PESO_ARISTA;
		
		bool NEXT = true;
		uint32 aristas_x = 0;
		uint32 sum_x_n = (nodos * (nodos - 1)) /2; 
		while (aristas) {
	
			MAX_PESO_ARISTA  = MAX_SUMA - (aristas - 1); 
			z = 1 + rand32() % MAX_PESO_ARISTA;

			if (NEXT) {
				NEXT = false;
				x++;
				y=0;
				
				sum_x_n -= x; 
			
				uint32 base = cotaInf(aristas, sum_x_n) + 1;
				uint32 offset = cotaSup(x,aristas, nodos) - cotaInf(aristas, sum_x_n);
				if (offset > 0)
					aristas_x =  base + rand32() % offset;
				else
					aristas_x = base;
						
			}
				if (!NEXT) {
					while ( !( rand32() % 2 ) && (aristas_x < (x-y)))
					y++;
									
				// usar ese nodo Y			
				aristas_x--;
				
			}
			G.agregarArista(x,y,z); //inserta arista
			
			y++;
			
			if (aristas_x == 0) NEXT = true;
				SUMA += z;
			MAX_SUMA -= z;
			aristas--;			
		}
		
		t.comenzar();		
		resolver(G);
		t.terminar();
		
		TT = TT + t.getTiempo();
		}		
		
		times_efijo << 2*nodos << ' '  << TT / REP << endl;
		clocks_efijo << 2*nodos << ' ' << t.getCiclos() << endl;
		
	}	
		
	times_vfijo.close();
	times_efijo.close();
	clocks_vfijo.close();
	clocks_efijo.close();

}


bool establecerMaximo( const char *str ) {
	if ( !str2int( str, &gMax ) ) {
		cerr << "Máximo no reconocido, debe ser un número entero.\n";
		return false;
	}
	return true;
}

bool establecerMinimo( const char *str ) {
	if ( !str2int( str, &gMin ) ) {
		cerr << "Mínimo no reconocido, debe ser un número entero.\n";
		return false;
	}
	return true;
}
